package org.aplombh.java.leetcode.all;

import org.aplombh.java.utils.Pair;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class _40组合总数Ⅱ {
    public static void main(String[] args) {
        List<List<Integer>> lists = new Solution40_1().combinationSum2(new int[]{2,5,2,1,2}, 5);
    }
}

class Solution40_1 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> combine = new ArrayList<>();
        List<Pair> nums = new ArrayList<>();

        Arrays.sort(candidates);

        for (int i = 0; i < candidates.length; i++) {
            if (i == 0 || candidates[i - 1] != candidates[i]) {
                nums.add(new Pair(candidates[i], 1));
            } else {
                nums.get(nums.size() - 1).r++;
            }
        }

        dfs(nums, 0, target, res, combine);
        return res;
    }

    public void dfs(List<Pair> nums, int idx, int target, List<List<Integer>> res, List<Integer> path) {
        // 满足条件
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 到最后一个
        if (idx == nums.size()) {
            return;
        }




        // 直接跳过
        dfs(nums, idx + 1, target, res, path);

        // 选择当前数
        int max = Math.min(target / nums.get(idx).getL(), nums.get(idx).getR());

        for (int i = 1; i <= max; i++) {
            path.add(nums.get(idx).getL());
            dfs(nums, idx + 1, target - i * nums.get(idx).getL(), res, path);
        }

        for (int i = 1; i <= max; i++) {
            path.remove(path.size() - 1);
        }

    }
}

class Solution40_2 {

    int[] count = new int[51];
    int[] usage = new int[51];

    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        for (int candidate : candidates)
            count[candidate]++;

        proceed(50, target);
        return res;
    }

    void proceed(int candidate, int target) {

        if (target == 0) {
            joinList();
            return;
        }
        if (candidate == 0) {
            return;
        }

        proceed(candidate - 1, target);

        int maxUsage = Math.min(count[candidate], target / candidate);

        for (int i = 1; i <= maxUsage; i++) {
            usage[candidate]++;
            target -= candidate;
            proceed(candidate - 1, target);
        }
        usage[candidate] = 0;
    }

    void joinList() {
        List<Integer> list = new LinkedList<>();
        for (int i = 1; i <= 50; i++) {
            for (int u = 0; u < usage[i]; u++) {
                list.add(i);
            }
        }
        res.add(list);
    }
}